package com.dexter.year2023.charpter1_linkedlist.level2.topic2_4双指针;

import com.dexter.year2023.charpter1_linkedlist.level1.Demo1.Node;

import static com.dexter.year2023.charpter1_linkedlist.level1.Demo1.initLinkedList;
import static com.dexter.year2023.charpter1_linkedlist.level1.Demo1.printLinkedList;

/**
 * LeetCode 61. 旋转链表
 * https://leetcode.cn/problems/rotate-list/
 * <p>
 * 给你一个链表的头结点 head ，旋转链表，将链表每个结点向右移动 k 个位置。
 * <p>
 * 示例 1：
 * 输入：head = [1,2,3,4,5], k = 2
 * 输出：[4,5,1,2,3]
 * 示例 2：
 * 输入：head = [0,1,2], k = 4
 * 输出：[2,0,1]
 * <p>
 * 提示：
 * 链表中结点的数目在范围 [0, 500] 内
 * -100 <= Node.val <= 100
 * 0 <= k <= 2 * 109
 *
 * @author Dexter
 */
public class Demo3RotateRight {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5};
        Node head = initLinkedList(a);
        int k = 2;

        // 本节方法，定义快慢指针
        head = roateRight(head, k);
        printLinkedList(head);
    }

    private static Node roateRight(Node head, int k) {
        // 判空
        if (head == null || k == 0) {
            return head;
        }
        // 遍历链表，求长度
        int len = 0;
        Node temp = head;
        while (temp != null) {
            temp = temp.next;
            len++;
        }
        // 再次确认k位置
        if (k % len == 0) {
            return head;
        }
        // 找到倒数第k个位置，链表调头
        Node slow = head, fast = head;
        while (k % len > 0) {
            fast = fast.next;
            k--;
        }
        // 走到 k 之前一位，方便断开【重点】
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        // 到位了，开始调整
        Node res = slow.next;
        slow.next = null;
        fast.next = head; // 连上头结点
        return res;
    }
}
